package _02_linked_list.exerc.palindrome;

import _02_linked_list.exerc.ListNode;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 20:28
 * 判断是否是回文链表，正序和倒序的节点值一样(二合一，提升执行效率)
 */
public class MyTest2 {
    @Test
    public void test() {
        ListNode list = ListNode.of(new int[]{1, 2, 3});
        ListNode list2 = ListNode.of(new int[]{1, 2, 1});
        ListNode list3 = ListNode.of(new int[]{1, 2, 2, 1});
        ListNode list4 = ListNode.of(new int[]{1, 2, 3, 2, 1});
        System.out.println(isPalindrome(list));
        System.out.println(isPalindrome(list2));
        System.out.println(isPalindrome(list3));
        System.out.println(isPalindrome(list4));
    }

    boolean isPalindrome(ListNode listNode) {
        if (listNode == null || listNode.next == null) {
            return true;
        }

        ListNode slow = listNode; // 慢指针
        ListNode fast = listNode; // 快指针
        ListNode t = null; // 新头
        ListNode n = listNode; // 旧头

        // 找到前半部分 t，与后半部分 slow
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 反转前半部分链表
            n.next = t;
            t = n;
            n = slow;
        }

        // 1,2,2,2,1
        if (fast != null) {
            // 如果链表长度是奇数，这里会将后半部分头向后移动一位，保证与前半部分平衡
            slow = slow.next;
        }

        // 将前半部分 t 与后半部分 slow 进行逐一比较
        while (t != null) {
            if (t.val != slow.val) {
                return false;
            }
            t = t.next;
            slow = slow.next;
        }
        return true;
    }
}
